#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10, INF = 0x3f3f3f3f;

int n;
int a[N];
int ans, len;

vector<int> g[N];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}


bool check (int c, int x)
{
    for (int i = 0; i < g[c].size(); i ++ )
        if (gcd(g[c][i], x) > 1) return false;
    return true;
}

void dfs(int u)
{
    if (u == n)
    {
        ans = min(ans, len);
        return ;
    }
    
    for (int i = 0; i < len; i ++)
        if (check(i, a[u]))
        {
            g[i].push_back(a[u]);
            dfs(u + 1);
            g[i].pop_back();
        }
    g[len ++ ].push_back(a[u]);
    dfs(u + 1);
    g[-- len].pop_back();
}

int main()
{
    ans = INF;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    dfs(0);
    cout << ans << endl;
    return 0;
}

